Light Detection and Ranging (LIDAR) is a remote sensing technology used to collect topographic data, for example. A conventional LIDAR system combines an optical laser with an optical receiver system, the laser generating an optical pulse that is transmitted downward from an aircraft or satellite (a non-terrestrial vehicle) overflying an terrestrial area of interest or even from a terrestrial vehicle which has a view of an terrestrial area of interest. The transmitted optical pulse reflects off an object on the ground or even the ground itself and returns to the receiver system. The receiver system accurately measures the travel time of the pulse from its transmission to its return to the receiver system and therefore the distance to the object or the ground from the vehicle (terrestrial or non-terrestrial) can be easily calculated given the fact that an optical pulse travels at the speed of light. Assuming the vehicle knows it current position (using a global positioning system and an inertial measurement unit (IMU) or other navigation means), utilizing the range to the object and a laser scan angle (if other than horizontal), the height of the various objects encountered (as well as the height of the ground when it is detected) can be collected in a very fine grid (dataset) over the terrestrial area of interest. The aircraft/satellite/vehicle position from its GPS and IMU or other navigation means supplies the x and y coordinates of the dataset and the height measured for each x, y coordinate position provides a corresponding z value in the dataset.
LIDAR is being used by the National Oceanic and Atmospheric Administration (NOAA) and NASA scientists to document, for example, topographic changes along shorelines. These datasets are collected with aircraft-mounted lasers presently capable of recording elevation measurements at a rate of 2,000 to 5,000 pulses per second and presently having a vertical precision of 15 centimeters (6 inches). After a baseline dataset has been created, follow-up flights can be used to detect shoreline changes, new streets and other topographic changes.
Recognizing, segmenting, and extracting roads, curbs, and medians from LIDAR datasets collected in urban environments is a critical technology for intelligence agencies in the automatic acquisition and updating of geographic information systems. Road and street grids also play an important and useful role in mission planning, mapping, traffic analysis, and navigation. Furthermore, awareness and understanding of vehicle surroundings is critical for driver assistance and avoiding accidents. Curb and median detection and awareness is useful in many applications such as navigation, driver assistance, aids for visually impaired, etc.
Most of the previous road detection work has focused on the detection of rural roads from low resolution vision sensors. These sensors are either mounted on satellites or high-flying UAVs. The underlying assumption in these approaches is that imaged street pixels are different from pixels of other features such as buildings, roofs, parking lots, etc. Aerial image analysis algorithms that use pixel classification schemes are used to detect roads and streets. Most approaches concentrate on starting with manually ascribed seed pixels which are grown into entire streets using pixel intensity coherence and contiguity constraints. Pixel classification methods, however, suffer from variations in illumination, viewing conditions, and road surface materials, and do not take into account the geometric properties of the road neighborhoods. Some of these approaches use training instances to learn the statistical characteristics of the road regions and use the elicited features to detect streets and roads. These systems, however, are not general enough and constrain themselves to a particular road type. In addition, most of the systems use monocular cameras and can only find streets and are not robust or do not find curbs and medians. Some systems use elaborate stereo cameras to detect curbs, but such systems have limited range. See:    1) 3D Laser-based obstacle detection for autonomous driving, Dirk Hahnel and Sebastian Thrun, IROS 2008.    2) Se S. and Brady M., Vision-based detection of kerbs and steps, British Machine Vision Conference, 1997.    3) Lu X. and Manduchi R., Detection and localization of curbs and stairways using stereo-vision, ICRA 2005.    4) W. S. Wijesoma, K. R. S. Kodagoda, and A. P. Balasuriya, Road Boundary detection and tracking using LIDAR sensors, IEEE Transactions on Robotics and Automation, 2004 20(3), 456-464.    5) E. D. Dickmanns and B. D. Mysliwetz, Recursive 3-D road and relative ego-state recognition, IEEE PAMI 1992 (14), 199-213.    6) S. Medasani and R. Krishnapuram, “Detection of the Number of components in Gaussian mixtures using agglomerative clustering,” Intl Conf. on Neural Networks, 1997, the disclosure of which is hereby incorporated herein by reference.
This disclosure relates to combining 3D LIDAR sensing with 2D/3D model detection methods in an attempt to find streets, curbs, and medians. The combination of robust and constrained mixture decomposition algorithms, and context-utilization for detection of curbs and medians operating on 3D LIDAR data is heretofore is believed to be unknown. The objective function used in the constrained mixture decomposition is also believed to be unknown in this context. The objective function used to cluster is known per se in the prior art but the constraints under which the technique is adapted to work with LIDAR point clouds to detect linear road-like objects is as disclosed herein is believed to be unknown.